from collections import deque


class ListNode:

    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:

    def reorderList(self, head: ListNode) -> None:
        node = head
        s = []
        while node:
            n = node
            node = node.next
            n.next = None
            s.append(n)
        node = ListNode()
        while len(s) > 0:
            node.next = s.pop(0)
            node = node.next
            if len(s) > 0:
                node.next = s.pop(-1)
                node = node.next


class Solution:

    def reorderList(self, head: ListNode) -> None:
        node = head
        s = deque()
        while node:
            n = node
            node = node.next
            n.next = None
            s.append(n)
        node = ListNode()
        while len(s) > 0:
            node.next = s.popleft()
            node = node.next
            if len(s) > 0:
                node.next = s.pop()
                node = node.next


class Solution:

    def reorderList(self, head: ListNode) -> None:
        node = head
        s = []
        while node:
            n = node
            node = node.next
            n.next = None
            s.append(n)
        node = ListNode()
        l, r = 0, len(s) - 1
        while l < r:
            node.next = s[l]
            node = node.next
            if l == r:
                break
            node.next = s[r]
            node = node.next
            l += 1
            r -= 1
        node.next = None